from typing import List


class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        def work_n(s, nums):
            ans = 0
            a = 0
            sum = 0
            for i, n in enumerate(nums):
                sum += n
                a += 1
                if sum >= s:
                    if ans == 0 or a < ans:
                        ans = a
                    while sum >= s:
                        sum -= nums[i - a + 1]
                        a -= 1
                        if sum >= s:
                            if ans == 0 or a < ans:
                                ans = a
            return ans

        def work_nlogn(s, nums):
            ans = 0
            ss = [0]
            l = len(nums)
            for i, n in enumerate(nums, 1):
                ss.append(ss[i-1] + n)

            def search(a, i, j, s):
                while i < j:
                    h = (i+j)//2
                    if a[h] < s:
                        i = h+1
                    else:
                        j = h
                return i if a[i] >= s else 0

            for i, n in enumerate(nums):
                u = search(ss, i, l, s+ss[i])
                if u == 0:
                    continue
                if ans == 0 or u-i < ans:
                    ans = u-i
            return ans

        return work_nlogn(s, nums)


questions = [
    {
        's': 7,
        'nums': [2, 3, 1, 2, 4, 3]
    }
]
solve = Solution()
for i, q in enumerate(questions):
    print('#{}:'.format(i))
    print(' s: {}\n nums: {}'.format(q['s'], q['nums']))
    print(' ans:', solve.minSubArrayLen(q['s'], q['nums']))

